package order;
/**
 * 快速选择
 * 用于求解 Kth Element 问题，也就是第 K 个元素的问题。
 *
 * 可以使用快速排序的 partition() 进行实现。需要先打乱数组，否则最坏情况下时间复杂度为 O(N2)。
 */
/**
 * 堆
 * 用于求解 TopK Elements 问题，也就是 K 个最小元素的问题。使用最小堆来实现 TopK 问题，
 * 最小堆使用大顶堆来实现，大顶堆的堆顶元素为当前堆的最大元素。实现过程：不断地往大顶堆中插入新元素，
 * 当堆中元素的数量大于 k 时，移除堆顶元素，也就是当前堆中最大的元素，
 * 剩下的元素都为当前添加过的元素中最小的 K 个元素。插入和移除堆顶元素的时间复杂度都为 log2N。
 *
 * 堆也可以用于求解 Kth Element 问题，得到了大小为 K 的最小堆之后，
 * 因为使用了大顶堆来实现，因此堆顶元素就是第 K 大的元素。
 *
 * 快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，
 * 所有小于等于 Kth Element 的元素都是 TopK Elements。
 *
 * 可以看到，快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 1. Kth Element
 * 215. Kth Largest Element in an Array (Medium)
 *
 * Input: [3,2,1,5,6,4] and k = 2
 * Output: 5
 *
 * 题目描述：找到倒数第 k 个的元素。
 */
public class Order1_findKthLargest {
    public static void main(String[] args) {
        /**
         *解法 1
         * 排序 ：时间复杂度 O(NlogN)，空间复杂度 O(1)
         */
        int[] nums = new int[]{3,2,1,5,6,4};
        int k = 2;
        Arrays.sort(nums);
        int result = nums[nums.length - k];
        /**
         * for each 循环练习
         * for (int i: nums){
         *   System.out.println(i);
         *   }
         */
        System.out.println("排序处理法结果为："+ result);

        /**
         * 解法 2
         * 堆 ：时间复杂度 O(NlogK)，空间复杂度 O(K)。
         */
        int[] nums2 = new int[]{3,2,1,5,6,4};
        //初始化队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue();
        ArrayList<Integer> list = new ArrayList<>();

        for (int val: nums2) {
            priorityQueue.add(val);
            if (priorityQueue.size() > k){ //维护堆的大小为k
                //System.out.println("取出顶前的顶：" + priorityQueue.peek());
                //去除元素，应该在是按照大小比较，将小的去除
                //该方法可用于从小到大排序
                int poll = priorityQueue.poll();
                list.add(poll);
            }
        }
        System.out.println("从队列中取出的数据：" + list );
        System.out.println("堆处理法结果为 ：" + priorityQueue.peek());

        /**
         * 解法 3
         * 快速选择 ：时间复杂度 O(N)，空间复杂度 O(1)
         */
        int k2 = nums2.length - k;
        int l = 0, h = nums2.length - 1;
        while (l<h){
            int j = partition(nums2, l, h);

            if (j == k2){
                break;
            }else if (j < k2){
                l = j + 1;
            }else {
                h = j - 1;
            }
        }
        System.out.println("快速排序方法处理结果：" + nums2[k2]);
    }
    /**
     * 快速排序方法
     *     注意，如果要在main方法中调用，则需要将以下方法设置为 static，
     *     因为static修饰的方法中，调用的方法必须是static
     */
    //快速排序方法，对一组数据进行快速排序
    public static int partition(int[] nums,int l,int h){
        int i = l,j = h+1;  //h起初为nums的长度
        while (true){
            //注意此处写法，其实为双指针新式进行比较
            while (nums[++i] < nums[l] && i<h);
            while (nums[--j] > nums[l] && j>l);
            if (i>=j){
                break;
            }
            //将比选中的数大的数，放在后边，将比选中的数小的数据，放在前边
            swap(nums,i,j);
        }
        //将小的数据与选中的数据进行交换，选中的数放在中部位置
        swap(nums,l,j);
        return j;
    }
    //交换方法
    public static void swap(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
